/*
插入排序

基本思想:每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。

具体步骤：
1.将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；
2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5.将新元素插入到该位置后；
6.重复步骤2~5。

最好时间复杂度：O(N)
最坏时间复杂度：O(N^2)
平均时间复杂度：O(N^2)
空间复杂度：O(1)

稳定排序：是
原地排序：是

*/

#include "../../include/common.h"


//直接插入排序函数 升序
void InsertSort(ElementType a[], int n)
{
    // 注意从第二个元素开始
    for(int i= 1; i<n; i++) {
        // 如果a[i-1]本来就是小于a[i]的，已完成插入，不需要做任何操作。

        // 当a[i]是较小的元素，需要从i向前找，找到合适的位置插入
        if (a[i] < a[i-1]) {
            int j= i-1;
            ElementType x = a[i];
            //在0到j-1的中找到 a[i-1]<a[i]的位置
            //从第j个元素开始，即i的前一个。找一个比i位置元素小的位置
            while(j>-1 && x < a[j]) {  //从后往前找合适的位置，在查找的同时，将数组中的元素进行后移操作，给插入元素腾出空间
                a[j+1] = a[j];
                j--;
            }

            //跳出循环时，找到了x > a[j] 的恰当位置
            a[j+1] = x;      //插入到正确位置
       }
   }
}


void InsertSort2(ElementType a[], int n)
{
    // 注意从第二个元素开始
    for(int i= 1; i<n; i++) {
        // 如果a[i-1]本来就是小于a[i]的，已完成插入，不需要做任何操作。

        // 当a[i]是较小的元素，需要从i向前找，找到合适的位置插入
        if (a[i] < a[i-1]) {
            ElementType x = a[i];
            //在0到j-1的中找到 a[i-1]<a[i]的位置
            //从第j个元素开始，即i的前一个。找一个比i位置元素小的位置
            int j;
            for (j=i-1; j>-1 && x<a[j]; j--)
                a[j+1] = a[j];

            //跳出循环时，找到了x > a[j] 的恰当位置
            a[j+1] = x;      //插入到正确位置
       }
   }
}

/**
 * 改进：折半插入排序
*/